import java.util.Arrays;

/**
 * 分治算法
 * 归并算法
 * 
 * 
 * 
 */
public class 分治算法demo {
    
    public static void main(String[] args) {
        
        try{


            int[] nums = new int[]{5, 3, 8, 4, 2};

            mergeSort(nums);


        }catch(Exception e){
            e.printStackTrace();
        }
    }

    private static void mergeSort(int[] nums){

        if(nums.length <= 1){

            return;
        }

        int len = nums.length;

        //二分法
        int middle = len / 2; //数组中间位置
        //分成 2 部分解析
        int[] left = new int[middle];
        int[] rightt = new int[len - middle];

        //填充数据
        for(int i=0; i<middle; i++){
            left[i] = nums[i];
        }

        for(int i=middle; i<len; i++){

            rightt[i-middle] = nums[i];

        }

        //二分法递归处理
        mergeSort(left);
        mergeSort(rightt);

        // Arrays.stream(nums).boxed().map(s -> s+", ").forEach(System.out::print);
        // System.out.println();

        // Arrays.stream(left).boxed().map(s -> s+", ").forEach(System.out::print);
        // System.out.println();

        // Arrays.stream(rightt).boxed().map(s -> s+", ").forEach(System.out::print);
        // System.out.println();

        merge(nums, left, rightt);
    }

    private static void merge(int[] arr, int[] left, int[] right){

        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }

        Arrays.stream(arr).boxed().map(s -> s+", ").forEach(System.out::print);
        System.out.println();

    }
}
